package org.shj.dhsjjg.mintree;

/**
 * 克鲁斯卡尔算法， 解决与Prim算法相同的问题，区别是： Kruskal算法用于稀疏图时效率高，
 * Prim算法用于稠密图时效率高
 * @author huangjian
 *
 */
public class Kruskal {

	public static void main(String[] args){
		//这里为方便起见，边的权值已经排好序了
		int[][] edgeArr = init();

		int MaxVex = 9;  //顶点个数

		//定义一数组用来判断边与边是否形成环路
		int[] parent = new int[MaxVex];
		int i, n, m;
		for(i = 0 ; i < MaxVex; i++){
			parent[i] = 0; //初始化数组值为0;
		}
		
		for(i = 0 ; i < edgeArr.length ; i++){ //循环每一条边
			n = find(parent, edgeArr[i][0]);
			m = find(parent, edgeArr[i][1]);
			if(n != m){ //此边与现有生成树没有形成环路
				parent[n] = m; //将此边的结尾顶点放入下标为起点的parent中，表示此顶点已经在生成树集合中
				System.out.println("(V" + edgeArr[i][0] + ",V" +edgeArr[i][1] + ")");
			}
		}
	}
	
	public static int find(int[] parent, int f){
		while(parent[f] > 0){
			f = parent[f];
		}
		return f;
	}
	
	//初始化边集数组，按权值由小到大排列。即所有两点之间的连线做为一条边
	public static int[][] init(){		
		int[][] edges = new int[][]{
			//begin, end, weight
				{4, 7, 7},
				{2, 8, 8},
				{0, 1, 10},
				{0, 5, 11},
				{1, 8, 12},
				{3, 7, 16},
				{1, 6, 16},
				{5, 6, 17},
				{1, 2, 18},
				{6,7, 19},
				{3, 4, 20},
				{3, 8, 21},
				{2, 3, 22},
				{3, 6, 24},
				{4, 5, 26}
		};
		
		return edges;
	}
}
